🔢 Count the Number of Arrays with K Matching Adjacent Elements LeetCode 3405 (C++ | Python | JavaScript)
LeetCode 3405 | Hard | Combinatorics
You are given three integers:
n: length of the array
m: range of values [1, m]
k: number of adjacent equal pairs
You must find the total number of "good arrays", where:
Every element lies in the range [1, m]
Exactly k indices i (where 1 ≤ i < n) satisfy arr[i - 1] == arr[i]
Since the result may be large, return the count modulo 10⁹ + 7.
To construct a valid array:
Pick k positions (from the n - 1 possible adjacent pairs) to be equal.
The first element can be any value from 1 to m.
For each of the n - 1 - k remaining positions (which must differ from the previous element), there are m - 1 options.
So, the total number of such arrays is:
C(n - 1, k) × m × (m - 1)^(n - 1 - k)
Where:
C(n - 1, k) is the number of ways to choose k adjacent positions to…
( 5
min )